#ifndef COMPAREGRAPH_H_
#define COMPAREGRAPH_H_

#include <boost/lexical_cast.hpp>
#include <boost/bind.hpp>

#include "graph_support/GraphSupport.h"

#include "graph_support/utils/test_my_graph/BoostTestUtils.h"
#include "graph_support/utils/GraphTemplateUtils.h"
#include "graph_support/utils/PtrAccessOpSimulator.h"


namespace GRAPH_SUPPORT_NS
{
namespace utils
{
namespace test_my_graph
{

/**
 * checks if grapg gr has at least same edges as graph pattern
 * returns count of found edges in pattern
 */
template< typename TstGrT, typename PttrnGrT >
size_t checkGraphSuperstructure( TstGrT & gr, PttrnGrT & pattern )
{
	typedef typename TstGrT::GrVertex GrVertex;
	typedef typename TstGrT::GrEdge GrEdge;
	typedef typename TstGrT::GrEdgePtr GrEdgePtr;
	typedef typename TstGrT::VertexIterator VertexIterator;
	typedef typename TstGrT::EdgeIterator EdgeIterator;
	typedef typename PttrnGrT::EdgeIterator PEdgeIterator;

	TEST_CASE_REQUIRES_RETST( gr.getVertexCount() == pattern.getVertexCount(),
			"sizes not equal: " + boost::lexical_cast< std::string >( gr.getVertexCount() ) +
			boost::lexical_cast< std::string >( pattern.getVertexCount() ), 0 );

	size_t n = gr.getVertexCount();
	size_t edgesFound = 0;
	std::vector< int > hasEdgeToBuf( n );
	int * hasEdgeTo = & hasEdgeToBuf[0];

	for ( VertexIterator vit = gr.getVerticesBeg(); vit != gr.getVerticesEnd(); ++vit )
	{
		GrVertex vertex = * vit;
		size_t vertexId = gr.vert2num( vertex );

		std::fill( hasEdgeTo, hasEdgeTo + n, 0 );
		for( EdgeIterator eit = gr.getEdgsBeg( vertex ); eit != gr.getEdgsEnd( vertex ); ++eit )
		{
			size_t endVid = ( * eit )->endId();
			assert( endVid != Graph::NOT_A_VERTEX_ID );
			hasEdgeTo[endVid]++;
			boost::optional< GrEdgePtr > found = utils::findEdge( gr, vertex, ( * eit )->end() );
			BOOST_CHECK( found );
			edgesFound++;
		}
		gr.forEachOutEdge( vertex,
				boost::bind( & incrOperator< int >, boost::bind( & accessOperator< int, int *, int >, hasEdgeTo,
						boost::bind( & GrEdge::endId, _1 ) ) ) );

		for( PEdgeIterator eit = pattern.getEdgsBegId( vertexId ); eit != pattern.getEdgsEndId( vertexId ); ++eit )
		{
			size_t endVid = ( * eit )->endId();
			BOOST_CHECK_MESSAGE( hasEdgeTo[endVid] > 0,
					std::string( "Graph was expected to have edge: " +
					boost::lexical_cast< std::string >( vertexId ) + " -> " +
					boost::lexical_cast< std::string >( endVid ) ) );
		}
	}

	return edgesFound;
}

}
}
}

#endif /* COMPAREGRAPH_H_ */
